Hashing: Estrategias de Redimensionamiento

La Necesidad de Rehashear

Para garantizar el rendimiento deseado de $O(1)$ en promedio para búsqueda e inserción, el Factor de Carga ( $\lambda = N/M$ ) debe estar estrictamente limitado, donde $N$ es el número de elementos y $M$ es la capacidad de la tabla.

Si $\lambda$ se permite crecer indefinidamente, las colisiones aumentan exponencialmente y la complejidad promedio del tiempo de ejecución degrada hacia $O(N)$ .

Condición	Acción Activada	Impacto
$\lambda < \lambda_{max}$	Estándar $O(1)$ inserción	Se mantiene la eficiencia óptima.
$\lambda \geq \lambda_{max}$	Redimensionamiento (Rehasheo)	Restaura $O(1)$ rendimiento, pero genera un costo temporal de $O(N)$ costo.

Valores Umbral Comunes ( $\lambda_{max}$ ): 0.70 a 0.75.

El Proceso de Redimensionamiento

El redimensionamiento requiere recalcular el índice de hash para cada elemento actualmente en la tabla, un proceso conocido como Rehasheo.

Determinación de Nueva Capacidad: Seleccione una nueva capacidad $M_{new}$ , generalmente el doble de la capacidad actual ( $M_{new} = 2M$ ). Esto asegura que el nuevo $\lambda$ sea la mitad del umbral crítico.
Creación de la Tabla: Asigne un nuevo arreglo de tabla hash de tamaño $M_{new}$ .
Iteración de Elementos: Recorra todos los $N$ elementos existentes en la tabla antigua.
Rehasheo: Para cada clave $k$ , calcule el nuevo índice usando el módulo actualizado: $\text{índice}' = h(k) \pmod{M_{new}}$
Inserción: Inserte el elemento en la nueva tabla en el $\text{índice}'$ .

Nota: Como el módulo cambia, copiar simplemente el arreglo es imposible; cada elemento debe ser reinsertado.

Costo Amortizado

¿Por qué el redimensionamiento es $O(N)$

El redimensionamiento requiere procesar todos los $N$ elementos, lo que significa que la operación misma toma $O(N)$ tiempo, lo cual viola temporalmente el objetivo de $O(1)$ inserción.

Análisis Amortizado

Utilizamos Análisis Amortizado para justificar este costo. Si la tabla duplica su tamaño cada vez que se redimensiona (crecimiento exponencial), el costo elevado de $O(N)$ se distribuye sobre un gran número de inserciones intermedias de $O(1)$ inserciones.

El costo promedio de cualquier inserción individual, considerando el redimensionamiento periódico, sigue siendo $O(N)$ redimensionamiento, permanece $O(1)$ .

📝 Cuestionario Interactivo

1. Un mapa hash tiene una capacidad $M=50$ y un factor de carga máximo $\lambda_{max} = 0.6$ . ¿En qué número de elementos ( $N$ ) debe activarse el redimensionamiento?

A) $N = 25$
B) $N = 30$
C) $N = 31$
D) $N = 50$

2. Durante un redimensionamiento, ¿por qué no podemos copiar simplemente los elementos de la tabla antigua a la nueva, más grande?

A) Es computacionalmente más lento que el rehasheo.
B) El índice de hash depende de la capacidad de la tabla ( $M$ ), la cual ha cambiado.
C) Generaría fragmentación de memoria.
D) Los datos antiguos están en estado de solo lectura.

3. ¿Cuál es la complejidad de tiempo amortizado de una inserción en una tabla hash que duplica su tamaño al redimensionarse?

A) $O(N)$
B) $O(1)$
C) $O(\log N)$
D) $O(N \log N)$

4. ¿Cuál es la consecuencia principal de no redimensionar una tabla hash cuando su factor de carga se vuelve demasiado alto?

A) El rendimiento degrada hacia $O(N)$ debido a un aumento de colisiones.
B) La tabla se agotará de memoria inmediatamente.
C) La función hash en sí misma se vuelve inválida.
D) La tabla elimina automáticamente los elementos más antiguos.